package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/20
 */
public class PBuildTree {

    public static void main(String[] args) {
        System.out.println(buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
    }

    static int index = 0;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }

    private static TreeNode buildTree(int[] preOrder, int[] inorder, int l, int r) {
        TreeNode ret = null;
        if ( l == r )
            ret = new TreeNode(preOrder[index++]);
        else if ( l < r ) {
            ret = new TreeNode(preOrder[index++]);
            int m = l;
            for (int i = l; i <= r; i++) {
                if (preOrder[index - 1] == inorder[i]) {
                    m = i;
                    break;
                }
            }
            ret.left = buildTree(preOrder, inorder, l, m - 1);
            ret.right = buildTree(preOrder, inorder, m + 1, r);
        }
        return ret;
    }

}
